IOI2022 Insects 高伪正解

注：本解答可能不是正解，但是分数是100 (?)

有的路原本不是路，走的路多了经成了路 — 沃.梓即硕德

题目链接: https://ioi2022.id/tasks/

通过人数：9/357

题目难度：CF2400

高伪解答

首先观察题目要求，大概是要求 \(O(N)\) 或者 \(O(N\log N)\) 级别的算法。

定义 \(\text{Group}\) 为不同的数字的个数。

定义 \(\text{MinSize}\) 为答案。

可以尝试找根号级别的分治算法，因为 \(\text{Groups}*\text{MinSize} >= N\)，相互是反比例关系。

算法1：当Group大的时候，考虑两两枚举放入机器。如果结果=2, 则数字一样。如果结果=1, 则数字不一样。算法复杂度\(O(\text{Group}N)\)

算法2：当MinSize大的时候，考虑枚举从小到大MinSize （因为MinSize是答案），如果机器返回的答案大于 \(\text{MinSize}\), 那么就可以考虑忽略掉。考虑做差即可。算法复杂度\(O(\text{MinSize}N)\)

根号分治可以得到 \(O(N \sqrt N)\).

考虑放弃根号算法，采取二分答案并且使用算法2. 放弃从小到大枚举，改成二分即可。删除和添加数字的时候，每次都可以排除一半的数字，记得打个记号，时间复杂度大概可以 \(T(3n)\).

但是喜提 99.556 分，怎么办呢？？？看起来已经没有优化的空间了？？？感觉故意被针对了？？？常数恰好比\(3\) 多了一点怎么办？

实际上可以乱搞搞，精髓是魔改后的二分：

1 2	srand(time(0)); int mid = (left+right+rand()%2)/2;

在一定概率下（?）可以省下很多时间。多提交几次炸炸评测机就行了。

当然我的细节还有很多，代码如下请自行体会：

#include"insects.h"
#include"bits/stdc++.h"
#include"random"
using namespace std;

const int maxn = 2005;
int ex[maxn];int ix[maxn];
int in[maxn];
int group;

void inside (int i) {
    in[i] = 1;
    move_inside(i);
}
void outside (int i) {
    in[i] = 0;
    move_outside(i);
}

int press () {
    return press_button();
}

vector<int> rem,sel;
int cnt;

int check (int mid, int N, bool flag) {
    rem.clear();
    if (!flag) sel.clear();
    for (int i=0;i<N;i++) {
        if (cnt==group*mid) break;
        if (in[i]||ex[i]) continue;
        inside(i);
        int w = press();
        if (w>mid) {
            outside(i);
            rem.push_back(i);
        }
        else {
            cnt++;
            sel.push_back(i);
        }
    }
    if (cnt==group*mid) return true;
    else return false;
}

void del (int N) {
    for (int i=0;i<N;i++) {
        if (in[i]&&!ix[i]) {
            outside(i);
            cnt--;
        }
    }
    for (int u:rem) ex[u] = 1;
}

void upd (int N) {
    for (int u:sel) ix[u] = 1;
}

int min_cardinality (int N) {
    srand(time(0));
    sel.push_back(0);
    inside(0); group++;cnt++;
    for (int i=1;i<N;i++) {
        inside(i);
        int w = press();
        if (w==1) {
            group++;
            cnt++;
            sel.push_back(i);
        }
        else outside(i);
    }
    if (group==N) return 1;
    int left = 1;int right = N/group;
    int ans = -1;
    while (left<=right) {
        int mid = (left+right+rand()%2)/2;
        if (check(mid,N,(left==1)&&(right==N/group))) {
            left = mid+1;
            ans = mid;
            upd(N);
        }
        else {
        	  right = mid-1;
            del(N);
        }
    }
    return ans;
}